package leetcode.shuangpoint;

/**
 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
 输出：[1,2,2,3,5,6]
 解释：需要合并 [1,2,3] 和 [2,5,6] 。
 合并结果是 [1,2,2,3,5,6]

 */
public class Merge {

    public static void main(String[] args) {
        int [] arr1 = new int[]{1,2,3,0,0,0};
        int [] arr2 = new int[]{2,5,6};

        new Merge().merge1(arr1,3,arr2,3);
        for (int i : arr1) {
            System.out.print(i+" ");
        }
    }

    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1,j=n-1,k=nums1.length-1;
        while (i>=0 && j>=0){
            if(nums1[i]>nums2[j]){
                nums1[k--] = nums1[i--];
            }else {
                nums1[k--] = nums2[j--];
            }
        }
        while (i>=0)
            nums1[k--] = nums1[i--];

        while (j>=0)
            nums1[k--] = nums2[j--];

    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
       int []arr = new int[nums1.length];

       int i = 0,j=0,k=0;
       while (i<m && j<n){
           if(nums1[i]<nums2[j]){
               arr[k++] = nums1[i++];
           }else {
               arr[k++] = nums2[j++];
           }
       }
       while (i<m)
           arr[k++] = nums1[i++];

        while (j<n)
            arr[k++] = nums2[j++];


        System.arraycopy(arr, 0, nums1, 0, arr.length);
    }

}